#ifndef GAMEENGINE_CORE_GRAPH_OCTREE_NODE_H
#define GAMEENGINE_CORE_GRAPH_OCTREE_NODE_H

#include <GameEngine/Core/core_settings.h>

#include <GameEngine/Geometry/Volumes/box3d.h>

#include <list>
#include <vector>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

template <class O> class OctreeNodeIterator;
template <class O> class OctreeNodeConstIterator;

//=====================================================================

namespace OctreeNodeItr {
	//! Enumerates the types of nodes on which it is possible to iterate in a octree
	enum OctreeNodeItrType {
		//! Iteration on all the nodes of the octree
		AllNodes,
		//! Iteration on the low-level nodes of the octree. Low-level nodes are nodes that do not have children
		LowLevelNodes,
		//! Iteration on the non-empty nodes of the octree
		NonEmptyNodes
	};
}

//=====================================================================

//! Class in charge of representing a node in an octree
/*!
 *  A node in an octree can recursively be subdivided into eight subnodes. Each
 *  octree node can contain some elements.
 *
 *  An octree node is templated by two parameters: E represents the type of elements
 *  stored by the octree and T represents the level of numerical precision required
 *  for space subdivision (T would typically either be of type float or double).
 */
template <class E, class T>
class OctreeNode {

public:
	//! Typedef used to handle number of elements
	typedef unsigned int ElementCount;

	//! Typedef used to iterate through nodes
	typedef OctreeNodeIterator<OctreeNode> Iterator;
	//! Typedef used to iterate through constant nodes
	typedef OctreeNodeConstIterator<OctreeNode> IteratorConst;

public:
	OctreeNode();
	OctreeNode(const Box3d<T>& box);
	OctreeNode(const OctreeNode& rhs);
	~OctreeNode();
	OctreeNode& operator=(const OctreeNode& rhs);

	OctreeNode* children() const;
	const Box3d<T>& box() const;

	const std::vector<E>& elements() const;
	std::vector<E>& elements();

	bool subdivide();
	bool merge(bool unique = true);

	bool add_element(const E& element, const Point3d<T>& location, bool unique = true);
	bool add_element(const E& element, const Box3d<T>& location);
	ElementCount remove_element(const E& element, bool recursive = true);
	bool find_element(const E& element, bool recursive = true) const;

	ElementCount nb_elements(bool recursive = true) const;

	bool is_non_empty() const;
	bool is_low_level() const;

	const OctreeNode* get_node(const Point3d<T>& location) const;
	OctreeNode* get_node(const Point3d<T>& location);
	std::list<const OctreeNode*> get_nodes(const Box3d<T>& location,
		OctreeNodeItr::OctreeNodeItrType type = OctreeNodeItr::LowLevelNodes) const;
	std::list<OctreeNode*> get_nodes(const Box3d<T>& location,
		OctreeNodeItr::OctreeNodeItrType type = OctreeNodeItr::LowLevelNodes);

protected:
	//! Typedef used to handle OctreeNode pointers
	typedef OctreeNode* SelfPtr;
	//! Typedef used to handle OctreeNode constant pointers
	typedef const OctreeNode* SelfPtrConst;

protected:
	bool add_element(const E& element, bool unique = true, bool check_children = true);

	static bool get_nodes_recursive(const OctreeNode& node, std::list<SelfPtrConst>& list,
		const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type);
	static bool get_nodes_recursive(OctreeNode& node, std::list<SelfPtr>& list,
		const Box3d<T>& location, OctreeNodeItr::OctreeNodeItrType type);

protected:
	//! Children nodes
	OctreeNode* children_;

	//! Valid box
	Box3d<T> box_;

	//! Elements
	std::vector<E> elements_;
};

//=====================================================================

//! Iterates through the children of an OctreeNode
/*!
 *  This iterator allows to iterate through the subnodes of an OctreeNode with three
 *  different manners: either iterate through all the nodes, all the low-level nodes
 *  (i.e., the nodes that do not have children) or all the non-empty nodes.
 *
 *  An example of such an iteration could be:
 *  @code
 *  OctreeNode<E,T> node = ...;
 *  
 *  for ( OctreeNode<E,T>::Iterator it(node); it.more(); it.next() ) {
 *		// Access current subnode
 *		OctreeNode<E,T>& current = it.cur();
 *  
 *		// do stuff...
 *  }
 *  @endcode
 *  Please note that in the example, the iterator is built as a OctreeNode<E,T>::Iterator
 *  object. This is a typedef provided in the OctreeNode class - in practice, this is strictly
 *  equivalent to OctreeNodeIterator< OctreeNode<E,T> > (although this is generally more
 *  convenient to type).
 *
 *  This class provides read-write access to the elements of the octree node. If
 *  you want read-only access, please use the OctreeNodeConstIterator class.
 *
 @note Any change in the OctreeNode object will invalidate all iterators using it. The
       behavior of the iterator is unpredictable in case of such a change.
 */
template <class O>
class OctreeNodeIterator {

public:
	OctreeNodeIterator(O& node, OctreeNodeItr::OctreeNodeItrType type = OctreeNodeItr::LowLevelNodes);
	~OctreeNodeIterator();

	bool more() const;
	void next();
	O& cur();
	const O& cur() const;

private:
	void push_node(O& node);
	void pop_node();

	void pop_node_low_level();
	void pop_node_all();
	void pop_node_non_empty();

private:
	//! Function pointer typedef used to call the correct pop function
	typedef void (OctreeNodeIterator::*POP_FUNC)();

private:
	//! Pop function
	POP_FUNC pop_func_;

	//! The current node of the iterator
	O* node_;

	//! The next node of the iterator
	O* next_node_;

	//! List of nodes
	std::list< std::pair<O*,int> > nodes_to_explore_;
};

//=====================================================================

//! Iterates through the children of an OctreeNode (constant iterator)
/*!
 *  This iterator allows to iterate through the subnodes of an OctreeNode with three
 *  different manners: either iterate through all the nodes, all the low-level nodes
 *  (i.e., the nodes that do not have children) or all the non-empty nodes.
 *
 *  An example of such an iteration could be:
 *  @code
 *  OctreeNode<E,T> node = ...;
 *  
 *  for ( OctreeNode<E,T>::IteratorConst it(node); it.more(); it.next() ) {
 *		// Access current subnode
 *		const OctreeNode<E,T>& current = it.cur();
 *  
 *		// do stuff...
 *  }
 *  @endcode
 *  Please note that in the example, the iterator is built as a OctreeNode<E,T>::IteratorConst
 *  object. This is a typedef provided in the OctreeNode class - in practice, this is strictly
 *  equivalent to OctreeNodeConstIterator< OctreeNode<E,T> > (although this is generally more
 *  convenient to type).
 *
 *  This class solely provides read-only access to the elements of the octree node. If
 *  you want read-write access, please use the OctreeNodeIterator class.
 *
 @note Any change in the OctreeNode object will invalidate all iterators using it. The
       behavior of the iterator is unpredictable in case of such a change.
 */
template <class O>
class OctreeNodeConstIterator {

public:
	OctreeNodeConstIterator(const O& node, OctreeNodeItr::OctreeNodeItrType type = OctreeNodeItr::LowLevelNodes);
	~OctreeNodeConstIterator();

	bool more() const;
	void next();
	const O& cur();

private:
	void push_node(const O& node);
	void pop_node();

	void pop_node_low_level();
	void pop_node_all();
	void pop_node_non_empty();

private:
	//! Function pointer typedef used to call the correct pop function
	typedef void (OctreeNodeConstIterator::*POP_FUNC)();

private:
	//! Pop function
	POP_FUNC pop_func_;

	//! The current node of the iterator
	const O* node_;

	//! The next node of the iterator
	const O* next_node_;

	//! List of nodes
	std::list< std::pair<const O*,int> > nodes_to_explore_;
};

//=====================================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#include <GameEngine/Core/Graph/octree_node.hpp>

#endif
